package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

import java.util.LinkedList;
import java.util.List;

/**
 * 错误写法, 会错意了, 题意要的path就是singlepath
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC437 implements TreeProblem {
    int result = 0;

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        rec(root, sum);
        return result;
    }

    //return 包含root的子树的singlepath的可能的sum列表
    public List<Integer> rec(TreeNode root, int sum) {
        if (root.val == sum)
            result++;

        int toCompose = sum - root.val;

        List<Integer> candidates = new LinkedList<>();
        candidates.add(root.val);
        List<Integer> leftCands = null, rightCands = null;
        if (root.left != null) {
            leftCands = rec(root.left, sum);
            for (Integer leftCan : leftCands) {
                candidates.add(leftCan + root.val);
                if (leftCan == toCompose)
                    result++;
            }
        }
        if (root.right != null) {
            rightCands = rec(root.right, sum);
            for (Integer rightCan : rightCands) {
                candidates.add(rightCan + root.val);
                if (rightCan == toCompose)
                    result++;
            }
        }
        if (leftCands != null && rightCands != null) {
            for (int i = 0; i < leftCands.size(); i++) {
                for (int j = 0; j < rightCands.size(); j++) {
                    if (leftCands.get(i) + rightCands.get(j) == toCompose)
                        result++;
                }
            }
        }

        return candidates;
    }

    public static void main(String[] args) {
//        Integer[] a = {1, 2, 4, 3, 5, 7, 10, 6, null, 8, null, 11, 9, 15, null, null, null, 12, null, null, null, 13, null, null, null, null, 14};
//        int tar = 13;
        Integer[] a = {10, 5, -3, 3, 2, null, 11, 3, -2, null, 1};
        int tar = 8;
        TreeNode treeNode = TreeNode.arrayToTreeNode(a);
        System.out.println(new LC437().pathSum(treeNode, tar));
    }
}
